package com.c2b.algorithm.leetcode.base;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * <a href="https://leetcode.cn/problems/most-frequent-subtree-sum/">出现次数最多的子树元素和(Most Frequent Subtree Sum)</a>
 * <p>给你一个二叉树的根结点 root ，请返回出现次数最多的子树元素和。如果有多个元素出现的次数相同，返回所有出现次数最多的子树元素和（不限顺序）。
 * <p>
 * 一个结点的 「子树元素和」 定义为以该结点为根的二叉树上所有结点的元素之和（包括结点本身）。</p>
 * <pre>
 * 示例 1：
 *      输入: root = [5,2,-3]
 *              5
 *             / \
 *            2  -3
 *      输出: [2,-3,4]
 *
 * 示例 2：
 *      输入: root = [5,2,-5]
 *              5
 *             / \
 *            2  -5
 *      输出: [2]
 * </pre>
 * <b>提示：</b>
 * <ul>
 *     <li>节点数在 [1, 10^4] 范围内</li>
 *     <li>-10^5 <= Node.val <= 10^5</li>
 * </ul>
 *
 * @author c2b
 * @since 2023/5/22 17:35
 */
public class LC0508FindFrequentTreeSum_M {
    Map<Integer, Integer> cnt = new HashMap<>();
    int maxCnt = 0;

    public int[] findFrequentTreeSum(TreeNode root) {
        dfs(root);
        List<Integer> list = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : cnt.entrySet()) {
            if (entry.getValue() == maxCnt) {
                list.add(entry.getKey());
            }
        }
        int[] ans = new int[list.size()];
        for (int i = 0; i < list.size(); ++i) {
            ans[i] = list.get(i);
        }
        return ans;
    }

    private int dfs(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int sum = root.val + dfs(root.left) + dfs(root.right);
        cnt.put(sum, cnt.getOrDefault(sum, 0) + 1);
        maxCnt = Math.max(maxCnt, cnt.get(sum));
        return sum;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(2);
        root.right = new TreeNode(-5);
        LC0508FindFrequentTreeSum_M lc0508FindFrequentTreeSum_m = new LC0508FindFrequentTreeSum_M();
        for (int i : lc0508FindFrequentTreeSum_m.findFrequentTreeSum(root)) {
            System.out.println(i);
        }
    }
}
